/**
 * 恢复二叉搜索树
 *
 * 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
 *
 * 示例 1：
 * 输入：root = [1,3,null,null,2]
 * 输出：[3,1,null,null,2]
 * 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
 *
 * 示例 2：
 * 输入：root = [3,1,4,null,null,2]
 * 输出：[2,1,4,null,null,3]
 * 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
 *
 * 提示：
 * 树上节点的数目在范围 [2, 1000] 内
 * -231 <= Node.val <= 231 - 1
 *
 * 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
 */

/**
 * 这里我们也是利用二叉搜索树的特性, 找到两个顺序不对的位置,
 * 这两个位置, 分别与后面一个数进行比较, 就可以发现, 后面一个
 * 数比前面一个数小, 这个就是突破口了
 * 这里要注意, 第一个是前面的数, 第二个数是后面一个数
 * 还有一个点要注意, 就是第一个数和第二个数是在一起被发现的, 就是
 * 中序遍历他们紧靠在一起的情况, 所以我们在第一次找的数的时候, 也要
 * 更新第二个位置, 要是后面还能找到第二个位置, 我们直接覆盖就可以了
 * 要是找不到第二个数的位置, 前面我们就已经更新过了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 进行前后比较的节点
    TreeNode prev = null;

    // 两个位置错了节点
    TreeNode tmp1 = null;
    TreeNode tmp2 = null;

    public void recoverTree(TreeNode root) {

        // 直接中序遍历
        dfs(root);

        if (tmp1 != null && tmp2 != null) {

            // 这里交换顺序我们只需要将里面节点的内容改掉就好了
            int tmp = tmp1.val;
            tmp1.val = tmp2.val;
            tmp2.val = tmp;
        }
    }

    private void dfs (TreeNode root) {

        if (root == null) {
            return;
        }

        dfs(root.left);

        // 这里第一次尽心比较, 记录第一个数
        if (prev == null) {
            prev = root;
        } else {

            // 不是第一次比较, 我们比较节点的大小
            if (prev.val > root.val) {

                // 不满足, 我们将第二个位置一起更新, 后面要是又找到了, 直接覆盖就可以了
                tmp2 = root;

                if (tmp1 == null) {
                    tmp1 = prev;
                }
            }

            // 更新前面节点的大小
            prev = root;
        }

        dfs(root.right);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}